home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / GW AdaEd 1.4.2 / GWAdaDemos / NYUDemos / TOPSORT.ADA < prev    next >
Encoding:
Text File  |  1993-01-31  |  1.4 KB  |  93 lines  |  [TEXT/GADA]
  1. with LIST_PACKAGE;
  2. with TEXT_IO; use TEXT_IO;
  3. procedure TOP_SORT is
  4.  
  5.     package INT_IO is new INTEGER_IO(INTEGER);
  6.     use INT_IO;
  7.  
  8.     package LIST_PACK is new LIST_PACKAGE(NATURAL);
  9.     use LIST_PACK;
  10.  
  11.     type PO_ITEM is 
  12.       record
  13.     COUNT : INTEGER := 0;
  14.     SUCC  : LIST := EMPTY_LIST;
  15.       end record;
  16.  
  17.     type PO_SET is array(NATURAL range <>) of PO_ITEM;
  18.  
  19.     NO_PRED : LIST := EMPTY_LIST;
  20.  
  21.     NUM : NATURAL;
  22.     NUM_OUT : INTEGER := 0;
  23.  
  24. begin
  25.  
  26.     put_line("Enter the size of the SET:");
  27.     get(NUM);
  28.  
  29.     declare
  30.  
  31.     subtype ELEM_RANGE is NATURAL range 1 .. NUM;
  32.  
  33.     SET : PO_SET(ELEM_RANGE);
  34.  
  35.     X, Y : ELEM_RANGE;
  36.  
  37.     begin
  38.     loop
  39.         begin
  40.         get(X);
  41.         get(Y);
  42.  
  43.         SET(Y).COUNT := SET(Y).COUNT + 1;
  44.  
  45.         APPEND(SET(X).SUCC, Y);
  46.  
  47.         exception
  48.  
  49.          when END_ERROR => exit;
  50.  
  51.         end;
  52.     end loop;
  53.  
  54.     for I in ELEM_RANGE loop
  55.  
  56.         if SET(I).COUNT = 0 then
  57.         APPEND(NO_PRED, I);
  58.         end if;
  59.  
  60.     end loop;
  61.  
  62.     while not IS_EMPTY(NO_PRED) loop
  63.  
  64.         REMOVE(NO_PRED, X);
  65.  
  66.         put(X);
  67.         new_line;
  68.         NUM_OUT := NUM_OUT + 1;
  69.  
  70.         while not IS_EMPTY(SET(X).SUCC) loop
  71.  
  72.         REMOVE(SET(X).SUCC, Y);
  73.         SET(Y).COUNT := SET(Y).COUNT - 1;
  74.  
  75.         if SET(Y).COUNT = 0 then
  76.             APPEND(NO_PRED, Y);
  77.         end if;
  78.  
  79.         end loop;
  80.  
  81.     end loop;
  82.  
  83.     end;
  84.  
  85.     new_line;
  86.     if NUM = NUM_OUT then
  87.     put_line("The set is topologically sorted");
  88.     else
  89.     put_line("The set is not partially ordered");
  90.     end if;
  91.  
  92. end TOP_SORT;
  93.